package hwTwo5;

import java.util.Arrays;

// 作业 2.5.4
public class RemoveDuplicate {
    public static String[] dedup(String[] a) {
        if (a == null || a.length == 0) {
            return new String[0]; // 如果数组为空，直接返回空数组
        }

        // 1. 自定义快速排序
        quickSort(a, 0, a.length - 1);

        // 2. 去重逻辑与之前相同
        int uniqueCount = 0;
        for (int i = 1; i < a.length; i++) {
            if (!a[i].equals(a[uniqueCount])) {
                uniqueCount++;
                a[uniqueCount] = a[i];
            }
        }

        // 3. 返回去重后的结果
        return Arrays.copyOf(a, uniqueCount + 1);
    }
    // 快速排序实现
    private static void quickSort(String[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }


    private static int partition(String[] arr, int low, int high) {
        String pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j].compareTo(pivot) <= 0) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(String[] arr, int i, int j) {
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    private static void printArray(String[] array) {
        System.out.print("[");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
    public static void main(String[] args) {
        // 测试输入数组
        String[] input = {"banana", "apple", "orange", "banana", "apple", "grape"};

        // 调用 dedup 方法
        String[] result = dedup(input);

        // 打印去重且有序的结果
        System.out.println("Deduplicated and Sorted Array:");
        System.out.println(Arrays.toString(result));
    }
}
